import gmpy2

if __name__ == '__main__':
	p = 7031743260418711566739098073564107978890224227121460343193226960817186184383270087476418117720536015735507487887746435223674467305567985714768646881875443
	q = 10518469826290824137244071184647466795966232103440910166409726732405364202243942197965652168418478497573810469491020503654343864609715458810525321440541527
	e = 2
	c = 135258457853291620572721004024920015499815847845811584839142576985971544135277241259156609029562372968515417947459821107108690546144324
	n = p * q
	c1 = gmpy2.powmod(c, (p + 1) // 4, p)
	c2 = gmpy2.powmod(c, (q + 1) // 4, q)
	cp1 = p - c1
	cp2 = q - c2
	t1 = gmpy2.invert(p, q)
	t2 = gmpy2.invert(q, p)
	m1 = (q * c1 * c2 + p * c2 * t1) % n
	m2 = (q * c1 * t2 + p * cp2 * t1) % n
	m3 = (q * cp1 * t2 + p * c2 * t1) % n
	m4 = (q * cp1 * t2 + p * cp2 * t1) % n
	print(bytes.fromhex(hex(m1)[2:]))
	print("-" * 30)
	print(bytes.fromhex(hex(m2)[2:]))
	print("-" * 30)
	print(bytes.fromhex(hex(m3)[2:]))
	print("-" * 30)
	print(bytes.fromhex(hex(m4)[2:]))
